﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics.Eventing.Reader;
using System.Runtime.CompilerServices;
using System.Text;
using System.Threading;

namespace Algorithm
{
    /// <summary>
    /// 数组
    /// </summary>
    public class ArrayAlgorithm
    {
        /// <summary>
        /// 36. 有效的数独
        /// </summary>
        /// <param name="board"></param>
        /// <returns></returns>
        public bool IsValidSudoku(char[][] board)
        {
            HashSet<char> hs=new HashSet<char>();
            for (int i = 0; i < board.Length; i++)
            {
               //test
            }
            return true;
        }

        /// <summary>
        /// 1. 两数之和
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="target"></param>
        /// <returns></returns>
        public int[] TwoSum(int[] nums, int target)
        {
            for (int i = 0; i < nums.Length-1; i++)
            {
                int flag = target - nums[i];
                for (int j = i + 1; j < nums.Length; j++)
                {
                    if (flag == nums[j])
                    {
                        return new int[]{i,j};
                    }
                }

            }
            return new int[]{0,1};
        }

        /// <summary>
        /// 283. 移动零
        /// </summary>
        /// <param name="nums"></param>
        public void MoveZeroes2(int[] nums)
        {
            if (nums == null || nums.Length == 0)
            {
                return;
            }
            int index = 0;
            for (int i = 0; i < nums.Length; i++)
            {
                if (nums[i] != 0)
                {
                    nums[index] = nums[i];
                    index++;
                }
            }
            while (index<nums.Length)
            {
                nums[index] = 0;
                index++;
            }
        }

        /// <summary>
        /// 283. 移动零
        /// </summary>
        /// <param name="nums"></param>
        public void MoveZeroes1(int[] nums)
        {
            for (int i = 0; i <= nums.Length-1; i++)
            {
                for (int j = 0; j < nums.Length-1; j++)
                {
                    if (nums[j] == 0)
                    {
                        nums[j] = nums[j + 1];
                        nums[j + 1] = 0;
                    }
                }
            }
           
        }

        /// <summary>
        /// 66. 加一
        /// </summary>
        /// <param name="digits"></param>
        /// <returns></returns>
        public int[] PlusOne(int[] digits)
        {
            for (int i = digits.Length - 1; i >=0; i--)
            {
                if (digits[i] != 9)
                {
                    digits[i] += 1;
                    return digits;
                }
                digits[i] = 0;
            }
            int[] arr = new int[digits.Length+1];
            arr[0] = 1;
            return arr;
        }

        /// <summary>
        /// 350. 两个数组的交集 II
        /// </summary>
        /// <param name="nums1"></param>
        /// <param name="nums2"></param>
        /// <returns></returns>
        public int[] Intersect(int[] nums1, int[] nums2)
        {
            List<int> arr=new List<int>();
            Array.Sort(nums1);
            Array.Sort(nums2);

            int i = 0;
            int j = 0;
            while (i<nums1.Length&&j<nums2.Length)
            {
                if (nums1[i] == nums2[j])
                {
                    arr.Add(nums1[i]);
                    i++;
                    j++;
                }else if (nums1[i] > nums2[j])
                {
                    j++;
                }else if (nums1[i] < nums2[j])
                {
                    i++;
                }
            }

            return arr.ToArray();

        }

        /// <summary>
        /// 136. 只出现一次的数字
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public int SingleNumber(int[] nums)
        {
            int serves = 0;
            for (int i = 0; i < nums.Length; i++)
            {
                serves = serves ^ nums[i];
            }
            return serves;
        }

        /// <summary>
        /// 217. 存在重复元素
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public bool ContainsDuplicate(int[] nums)
        {
            int length = nums.Length;
            var hashSet = new HashSet<int>();

            if (length == 1)
            {
                return false;
            }

            for (int i = 0; i < length; i++)
            {
                hashSet.Add(nums[i]);
            }

            if (hashSet.Count == length)
            {
                return false;
            }
            return true;
        }

        /// <summary>
        /// 冒泡排序
        /// </summary>
        /// <param name="nums"></param>
        public void Maobao(int[] nums)
        {
            for (int i = 0; i <= nums.Length - 1; i++)
            {
                for (int j = i; j < nums.Length - 1; j++)
                {
                    if (nums[j] > nums[j + 1])
                    {
                        int temp = nums[j];
                        nums[j] = nums[j + 1];
                        nums[j + 1] = temp;
                    }
                }
            }
            foreach (var num in nums)
            {
                Console.WriteLine(num);
            }

        }

        /// <summary>
        /// 189. 旋转数组2
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="k"></param>
        /// <returns></returns>
        public int[] Rotate2(int[] nums, int k)
        {
            int length = nums.Length;
            k %= length;
            Reverse(nums, 0, nums.Length - 1);
            Reverse(nums, 0, k - 1);
            Reverse(nums, k, nums.Length - 1);
            foreach (var num in nums)
            {
                Console.WriteLine(num);
            }
            return nums;
        }

        private void Reverse(int[] nums, int top, int bottom)
        {
            while (top < bottom)
            {
                int temp = nums[top];
                nums[top++] = nums[bottom];
                nums[bottom--] = temp;
            }

        }

        /// <summary>
        /// 189. 旋转数组1
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="k"></param>
        /// <returns></returns>
        public int[] Rotate1(int[] nums, int k)
        {
            int[] arr = new int[nums.Length];
            int length = nums.Length;

            for (int i = 0; i < length; i++)
            {
                arr[(i + k) % length] = nums[i];
            }

            for (int i = 0; i < arr.Length; i++)
            {
                Console.WriteLine(arr[i]);
            }
            return nums;
        }

        /// <summary>
        /// 122. 买卖股票的最佳时机 II
        /// </summary>
        /// <param name="prices"></param>
        /// <returns></returns>
        public int MaxProfit(int[] prices)
        {
            int sum = 0;
            for (int i = 1; i < prices.Length; i++)
            {
                sum += Math.Max(prices[i] - prices[i - 1], 0);
            }

            return sum;

        }

        /// <summary>
        /// 26. 删除有序数组中的重复项
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public int RemoveDuplicates(int[] nums)
        {
            int i = 0;
            for (int j = 1; j < nums.Length; j++)
            {
                if (nums[i] != nums[j])
                {
                    i++;
                    nums[i] = nums[j];
                }
            }
            return i + 1;
        }
    }
}
